근사 알고리즘

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.

1. 개요
2. 근사 비율
3. 근사 알고리즘 설계 기법
4. 근사 알고리즘의 종류
5. 성능 보장
6. 근사 불가능성
- 6.1. 비 거리 공간 외판원 문제의 근사 불가능성
7. 응용 사례
8. 한계 및 현실성
참조

1. 개요

근사 알고리즘은 최적화 문제의 근사해를 구하는 알고리즘으로, 특히 NP-난해 문제에 유용하게 사용된다. 알고리즘이 출력하는 해의 목적 함수 값과 최적해의 목적 함수 값의 비율인 근사 비율을 통해 성능을 평가하며, 정밀도 보장 근사 알고리즘과 발견적 기법으로 나뉜다. 근사 알고리즘 설계에는 탐욕 알고리즘, 지역 탐색, 동적 계획법, 선형 계획법 완화 등의 기법이 활용된다. 성능은 상대적, 절대적, 점근적 성능 보장으로 나타낼 수 있으며, 근사 불가능성도 연구된다. 근사 알고리즘은 조합 최적화 문제에 응용되며, 실용적인 한계도 존재하지만, 이론적인 연구를 통해 실용적인 알고리즘 개선에 기여하기도 한다.

더 읽어볼만한 페이지

근사 알고리즘 - 최근접 이웃 탐색
최근접 이웃 탐색은 다차원 공간에서 주어진 질의와 가장 유사한 데이터를 찾는 최적화 문제로, 데이터 압축, 데이터 마이닝, 기계 학습 등 다양한 분야에서 활용되며, 효율적인 탐색을 위해 다양한 알고리즘이 개발되고 있고, 개인 정보 보호 및 데이터 편향성과 같은 윤리적 문제에 대한 고려도 중요해지고 있다.
근사 알고리즘 - 크리스토피데스 알고리즘
크리스토피데스 알고리즘은 삼각 부등식을 만족하는 완전 그래프에서 외판원 문제의 근사해를 구하는 O(n³) 복잡도의 알고리즘으로, 최소 비용 신장 트리 생성, 홀수 차수 정점 집합 식별, 최소 가중치 완전 매칭 계산을 통해 해밀턴 회로를 구성하며 최적해의 3/2 이내의 근사 비율을 보장하고 다양한 분야에 응용된다.
계산 복잡도 이론 - 양자 컴퓨터
양자 컴퓨터는 양자역학적 현상을 이용하여 정보를 처리하는 컴퓨터로, 큐비트를 통해 0과 1을 동시에 표현하여 특정 연산에서 기존 컴퓨터보다 빠른 속도를 보이며 암호 해독, 신약 개발 등 다양한 분야에 혁신을 가져올 것으로 기대된다.
계산 복잡도 이론 - 선형 시간
선형 시간은 알고리즘의 실행 시간이 입력 크기에 비례하여 증가하는 것을 의미하며, O(n)의 시간 복잡도를 가지는 알고리즘 분석의 중요한 척도로 활용된다.

근사 알고리즘
개요
분야	계산 복잡도 이론, 알고리즘
문제 유형	최적화 문제
관련 항목	NP-완전, 다항 시간 근사 스킴
정의
설명	최적해를 구하기 어려운 최적화 문제에 대해, 최적해에 "가까운" 해를 다항 시간 내에 찾아내는 알고리즘
목표	주어진 시간 안에 '충분히 좋은' 해답을 찾는 것
특징
장점	최적해를 구하는 데 너무 많은 시간이 소요되는 문제를 해결 가능 현실적인 제약 조건 하에서 실행 가능한 해결책 제공
단점	항상 최적의 해를 보장하지 않음
성능 측정
근사 비율 (Approximation Ratio)	알고리즘이 찾아낸 해의 품질을 최적해와 비교하는 척도
성능 보장	알고리즘이 반환하는 해가 최적해에서 얼마나 벗어나는지 이론적으로 보장
설계 기법
그리디 알고리즘 (Greedy Algorithm)	각 단계에서 가장 좋아 보이는 것을 선택하는 방식
동적 계획법 (Dynamic Programming)	부분 문제의 최적 해를 이용하여 전체 문제의 최적 해를 구하는 방식
선형 계획 완화 (Linear Programming Relaxation)	선형 계획 문제로 변환하여 해결하는 방식
반정부호 계획법 (Semidefinite Programming)	반정부호 계획법을 이용하여 해결하는 방식
무작위화 (Randomization)	무작위 선택을 사용하여 해를 탐색하는 방식
주요 알고리즘
Christofides 알고리즘	외판원 문제에 대한 1.5-근사 알고리즘
Goemans-Williamson 알고리즘	최대 컷 문제에 대한 근사 알고리즘
적용 분야
스케줄링	작업 스케줄링 문제
네트워크 설계	네트워크 최적 설계 문제
위치 결정	최적의 위치 결정 문제

2. 근사 비율

어떤 최적화 문제에 대해, 항상 $\rho$ 배를 벗어나지 않는 근사해를 구하는 알고리즘이 존재할 경우, 그 알고리즘을 ''' $\rho$ -근사 알고리즘'''이라고 부른다. 즉, 최적해가 OPT일 경우, 근사 알고리즘 $f(x)$ 는 항상 다음을 만족해야 한다.

$\mathrm{OPT}(x) \leq f(x) \leq \rho \mathrm{OPT}(x)$ ( $\rho > 1$ 인 경우)
$\rho \mathrm{OPT}(x) \leq f(x) \leq \mathrm{OPT}(x)$ ( $\rho < 1$ 인 경우)

근사 알고리즘의 간단한 예시는 최소 정점 덮개 문제에 대한 알고리즘이다. 입력 그래프의 모든 간선이 적어도 하나의 선택된 정점을 포함하도록 가장 작은 정점 집합을 선택하는 것이 목표이다. 정점 덮개를 찾는 한 가지 방법은 덮이지 않은 간선을 찾고, 해당 간선의 양쪽 끝점을 덮개에 추가하고, 해당 정점에 인접한 모든 간선을 그래프에서 제거하는 과정을 반복하는 것이다. 입력 그래프의 모든 정점 덮개는 해당 과정에서 고려된 각 간선을 덮기 위해 서로 다른 정점을 사용해야 하므로 (매칭) 생성된 정점 덮개는 최적의 덮개보다 최대 두 배 클 뿐이다. 즉, 이는 근사 계수가 2인 상수-인자 근사 알고리즘이다. 최근 고유 게임 추측에 따르면 이 인자가 심지어 가능한 최선이다.^[5]

NP-난해 문제는 근사 가능성에서 크게 다르다. 일부 문제는 배낭 문제와 같이 임의의 고정된

\epsilon > 0

에 대해 곱셈 인자

1 + \epsilon

내에서 근사될 수 있으므로 최적에 임의로 가까운 솔루션을 생성한다(이러한 근사 알고리즘 패밀리를 다항 시간 근사 방식 또는 PTAS라고 부른다). 다른 문제는 P = NP가 아닌 한 상수 또는 다항 인자 내에서 근사하는 것이 불가능하며, 이는 최대 클릭 문제의 경우와 같다. 따라서 근사 알고리즘을 연구하는 중요한 이점은 NP-완전성 이론에서 제공하는 것 이상으로 다양한 NP-난해 문제의 어려움을 세분화하여 분류하는 것이다. 즉, NP-완전 문제는 정확한 솔루션 관점에서 서로 (다항 시간 환원 하에서) 동일할 수 있지만, 해당 최적화 문제는 근사 솔루션 관점에서 매우 다르게 동작한다.

최적화 문제

\Pi: I \times S

가 주어졌을 때,

\Pi

는 근사 문제이고,

I

는 입력 집합,

S

는 해 집합이며, 비용 함수는

c: S \rightarrow \mathbb{R}^+

로 정의할 수 있다. 그리고 실행 가능한 해의 집합은

\forall i \in I, S(i) = {s \in S: i\Pi_s}

로 정의할 수 있다. 최대화 또는 최소화 문제에 대한 최적의 해

s^*

는

s^* \in S(i)

,

c(s^*) = min/max \ c(S(i))

와 같다.

실행 가능한 해

s \in S(i)

가 주어졌을 때,

s \neq s^*

이고, 해의 품질에 대한 보장, 즉 보장되어야 하는 성능(근사 계수)을 원할 것이다.

구체적으로, 알고리즘

A_{\Pi}(i) \in S_i

가 있을 때,

\forall i \in I \ s.t. |i| = n

에 대해 다음이 성립한다면 알고리즘은 '''근사 계수''' (또는 '''근사 비율''')

\rho(n)

을 갖는다.

''최소화'' 문제의 경우: $\frac{c(A_{\Pi}(i))}{c(s^*(i))}\leq\rho(n)$ , 즉 알고리즘이 선택한 해를 최적의 해로 나눈 값이 $\rho(n)$ 의 비율을 달성한다는 의미이다.
''최대화'' 문제의 경우: $\frac{c(s^*(i))}{c(A_{\Pi}(i))}\leq\rho(n)$ , 즉 최적의 해를 알고리즘이 선택한 해로 나눈 값이 $\rho(n)$ 의 비율을 달성한다는 의미이다.

알고리즘이 근사 한계에서 작동하는 인스턴스가 존재함을 입증하여 근사가 "타이트"(''타이트 근사'')함을 증명할 수 있으며, 이는 경계의 타이트함을 나타낸다. 이 경우, 알고리즘을 최악의 시나리오로 강제하도록 설계된 입력 인스턴스를 구성하는 것으로 충분하다.

문헌에서, 최댓값 (최솟값) 문제에 대한 근사 비율 ''c'' - ϵ (최솟값: ''c'' + ϵ)는 알고리즘이 임의의 ϵ > 0에 대해 ''c'' ∓ ϵ의 근사 비율을 가지지만, ϵ = 0에 대해서는 비율이 입증되지 않았거나 입증될 수 없음을 의미한다. 이의 예시는 요한 하스타드에 의한 충족 가능한 MAX-3SAT 인스턴스에 대한 최적의 비근사성—근사의 부존재—비율인 7/8 + ϵ이다.^[14] ''c'' = 1일 때, 해당 문제는 다항 시간 근사 알고리즘을 갖는다고 한다.

ϵ-항은 근사 알고리즘이 곱셈 오차와 상수 오차를 모두 도입하는 동시에 크기 ''n''인 인스턴스의 최소 최적값이 ''n''이 증가함에 따라 무한대로 갈 때 나타날 수 있다. 이 경우, 근사 비율은 ''c'' ∓ ''k'' / OPT = ''c'' ∓ o(1)이며, 여기서 ''c''와 ''k''는 상수이다. 임의의 ϵ > 0이 주어지면, 충분히 큰 ''N''을 선택하여 모든 ''n ≥ N''에 대해 항 ''k'' / OPT < ϵ이 되도록 할 수 있다. 고정된 모든 ϵ에 대해, 크기 ''n < N''인 인스턴스는 무차별 대입으로 해결할 수 있으므로, 모든 ϵ > 0에 대해 ''c'' ∓ ϵ의 근사 비율—근사 알고리즘의 존재와 보장—을 보여준다.

근사 알고리즘 중, 알고리즘이 출력하는 해의 목적 함수 값과 최적해의 목적 함수 값의 비(근사도)가 특정 범위 내에 들어가는 것이 보장되는 것을 특히 정밀도 보장 근사 알고리즘이라고 부른다. 그러한 보장이 없는 알고리즘은 발견적 기법 (휴리스틱스)이라고 불린다. 전자와 후자를 구분하여, 전자만을 근사 알고리즘이라고 부르는 경우도 있다.

예를 들어, 최소 정점 피복 문제에는 근사도 2의 단순한 알고리즘이 존재하지만, 근사도가 상수인 다항 시간 알고리즘이 존재하지 않는다고 여겨지는 문제도 있다.

3. 근사 알고리즘 설계 기법

근사 알고리즘을 설계하기 위해 현재 여러 가지 확립된 기법들이 있다. 여기에는 다음이 포함된다.

# 탐욕 알고리즘

# 지역 탐색

# 열거 및 동적 계획법 (이는 또한 매개변수 근사에 자주 사용된다.)

# 볼록 계획법 완화를 해결하여 분수 해를 얻는다. 그런 다음 이 분수 해를 적절한 반올림을 통해 실행 가능한 해로 변환한다. 널리 사용되는 완화에는 다음이 포함된다.

#* 선형 계획법 완화

#* 반정부호 계획법 완화

# 주-쌍대 방법

# 쌍대 적합

# 문제를 일부 메트릭에 임베딩한 다음 해당 메트릭에서 문제를 해결한다. 이는 메트릭 임베딩이라고도 한다.

# 무작위 표본 추출 및 위의 방법과 함께 일반적으로 무작위성을 사용.

근사 알고리즘 중, 알고리즘이 출력하는 해의 목적 함수 값과 최적해의 목적 함수 값의 비(근사도)가 특정 범위 내에 들어가는 것이 보장되는 것을 특히 정밀도 보장 근사 알고리즘이라고 부른다. 그러한 보장이 없는 알고리즘은 발견적 기법 (휴리스틱스)이라고 불린다. 전자와 후자를 구분하여, 전자만을 근사 알고리즘이라고 부르는 경우도 있다.

4. 근사 알고리즘의 종류

근사 알고리즘을 설계하기 위해 현재 여러 가지 확립된 기법들이 있다. 여기에는 다음이 포함된다.

# 탐욕 알고리즘

# 지역 탐색

# 열거 및 동적 계획법 (이는 또한 매개변수 근사에 자주 사용된다.)

# 볼록 계획법 완화를 해결하여 분수 해를 얻는다. 그런 다음 이 분수 해를 적절한 반올림을 통해 실행 가능한 해로 변환한다. 널리 사용되는 완화에는 다음이 포함된다.

#* 선형 계획법 완화

#* 반정부호 계획법 완화

# 주-쌍대 방법

# 쌍대 적합

# 문제를 일부 메트릭에 임베딩한 다음 해당 메트릭에서 문제를 해결한다. 이는 메트릭 임베딩이라고도 한다.

# 무작위 표본 추출 및 위의 방법과 함께 일반적으로 무작위성의 사용.

근사 알고리즘 중, 알고리즘이 출력하는 해의 목적 함수 값과 최적해의 목적 함수 값의 비(근사도)가 특정 범위 내에 들어가는 것이 보장되는 것을 특히 정밀도 보장 근사 알고리즘이라고 부른다. 그러한 보장이 없는 알고리즘은 발견적 기법(휴리스틱스)이라고 불린다. 전자와 후자를 구분하여, 전자만을 근사 알고리즘이라고 부르는 경우도 있다.

예를 들어, 최소 정점 피복 문제에는 근사도 2의 단순한 알고리즘이 존재하지만, 근사도가 상수인 다항 시간 알고리즘이 존재하지 않는다고 여겨지는 문제도 있다.

5. 성능 보장

어떤 최적화 문제에 대해, 항상 ρ배를 벗어나지 않는 근사해를 구하는 알고리즘이 존재할 경우, 그 알고리즘을 '''ρ-근사 알고리즘'''이라고 부른다.

최적해가 OPT일 때, 근사 알고리즘 f(x)는 항상 다음을 만족해야 한다.^[5]

$\mathrm{OPT}(x) \leq f(x) \leq \rho \mathrm{OPT}(x)$ ( $\rho > 1$ 인 경우)
$\rho \mathrm{OPT}(x) \leq f(x) \leq \mathrm{OPT}(x)$ ( $\rho < 1$ 인 경우)

크리스토피데스 알고리즘은 거리 공간 외판원 문제에서 근사해를 구하는 근사 알고리즘이다. 이 알고리즘은 최대 최적해의 3/2배 길이 안에 근사해를 구할 것을 보장하며, 1976년 Nicos Christofides에 의해 개발되었다. 2017년까지도 특정 조건에서의 거리 공간 외판원 문제를 제외한 일반 거리 공간 외판원 문제를 해결하는 가장 좋은 근사해라고 알려져 있다.

근사 알고리즘의 예시로는 최소 정점 덮개 문제가 있다. 이 문제는 입력 그래프의 모든 간선이 적어도 하나의 선택된 정점을 포함하도록 가장 작은 정점 집합을 선택하는 것이 목표이다.

NP-난해 문제는 근사 가능성에서 크게 다르다. 일부 문제는 배낭 문제와 같이 임의의 고정된

\epsilon > 0

에 대해 곱셈 인자

1 + \epsilon

내에서 근사될 수 있어, 최적에 임의로 가까운 솔루션을 생성한다. 이러한 근사 알고리즘 패밀리를 다항 시간 근사 방식(PTAS)라고 부른다. 다른 문제는 P = NP가 아닌 한 상수 또는 다항 인자 내에서 근사하는 것이 불가능하며, 이는 최대 클릭 문제의 경우와 같다.

근사 알고리즘을 연구하는 중요한 이점은 NP-완전성 이론에서 제공하는 것 이상으로 다양한 NP-난해 문제의 어려움을 세분화하여 분류하는 것이다. 즉, NP-완전 문제는 정확한 솔루션 관점에서 서로 (다항 시간 환원 하에서) 동일할 수 있지만, 해당 최적화 문제는 근사 솔루션 관점에서 매우 다르게 동작한다.

최적화 문제

\Pi: I \times S

가 주어졌을 때 (여기서

\Pi

는 근사 문제,

I

는 입력 집합,

S

는 해 집합), 비용 함수는

c: S \rightarrow \mathbb{R}^+

로, 실행 가능한 해의 집합은

\forall i \in I, S(i) = {s \in S: i\Pi_s}

로 정의할 수 있다. 최대화 또는 최소화 문제에 대한 최적의 해

s^*

는

s^* \in S(i)

,

c(s^*) = min/max \ c(S(i))

를 만족한다.

실행 가능한 해

s \in S(i)

가 주어졌을 때 (

s \neq s^*

), 해의 품질에 대한 보장, 즉 보장되어야 하는 성능(근사 계수)을 원하게 된다. 알고리즘

A_{\Pi}(i) \in S_i

가 있을 때,

\forall i \in I \ s.t. |i| = n

에 대해 다음이 성립한다면 알고리즘은 '''근사 계수''' (또는 '''근사 비율''')

\rho(n)

을 갖는다.

''최소화'' 문제의 경우: $\frac{c(A_{\Pi}(i))}{c(s^*(i))}\leq\rho(n)$
''최대화'' 문제의 경우: $\frac{c(s^*(i))}{c(A_{\Pi}(i))}\leq\rho(n)$

알고리즘이 근사 한계에서 작동하는 인스턴스가 존재함을 입증하여 근사가 "타이트"(''타이트 근사'')함을 증명할 수 있다.

근사 알고리즘 중, 알고리즘이 출력하는 해의 목적 함수 값과 최적해의 목적 함수 값의 비(근사도)가 특정 범위 내에 들어가는 것이 보장되는 것을 특히 정밀도 보장 근사 알고리즘이라고 부른다. 그러한 보장이 없는 알고리즘은 발견적 기법(휴리스틱스)이라고 불린다.

근사 알고리즘은 주로 다항 시간 내에 엄밀하게 풀기 어려운 NP-난해 문제에 대해 고안되지만, 다항 시간 내에 계산 가능한 문제에 대해서도 더 빠른 계산 시간으로 해를 구하려는 목적으로 사용되기도 한다.

5. 1. 상대적 성능 보장

어떤 최적화 문제에 대해, 항상

\rho

배를 벗어나지 않는 근사해를 구하는 알고리즘이 존재할 경우, 그 알고리즘을 '''

\rho

-근사 알고리즘'''이라고 부른다. 즉, 최적해가 OPT일 경우, 근사 알고리즘

f(x)

는 항상 다음을 만족해야 한다.^[5]

$\mathrm{OPT}(x) \leq f(x) \leq \rho \mathrm{OPT}(x)$ ( $\rho > 1$ 인 경우)
$\rho \mathrm{OPT}(x) \leq f(x) \leq \mathrm{OPT}(x)$ ( $\rho < 1$ 인 경우)

예를 들어 최소 정점 덮개 문제에서, 정점 덮개를 찾는 한 가지 방법은 덮이지 않은 간선을 찾아 해당 간선의 양쪽 끝점을 덮개에 추가하고, 해당 정점에 인접한 모든 간선을 그래프에서 제거하는 과정을 반복하는 것이다. 입력 그래프의 모든 정점 덮개는 해당 과정에서 고려된 각 간선을 덮기 위해 서로 다른 정점을 사용해야 하므로 (매칭) 생성된 정점 덮개는 최적의 덮개보다 최대 두 배 크다. 즉, 이는 근사 계수가 2인 상수-인자 근사 알고리즘이다.^[5]

'''상대적 성능 보장'''(relative performance guarantee)은 이 인자 ''ρ''를 말한다. 근사 알고리즘은 모든 인스턴스 ''x''에 대해 다음이 증명된 경우 '''절대적 성능 보장''' 또는 '''유계 오차''' ''c''를 갖는다.

:

(\mathrm{OPT} - c) \leq f(x) \leq (\mathrm{OPT} + c).

인스턴스 ''x''에 대한 솔루션 ''y''의 '''성능 보장''' ''R''(''x,y'')는 다음과 같이 정의된다.

:

R(x,y) =  \max \left ( \frac{OPT}{f(y)}, \frac{f(y)}{OPT} \right ),

여기서 ''f''(''y'')는 인스턴스 ''x''에 대한 솔루션 ''y''의 값/비용이다. 분명히, 성능 보장은 1보다 크거나 같으며, ''y''가 최적의 솔루션인 경우에만 1과 같다. 알고리즘 ''A''가 최대 ''r''(''n'')의 성능 보장을 가진 솔루션을 반환하도록 보장하는 경우, ''A''는 ''r''(''n'')-근사 알고리즘이라고 하며 ''근사 비율'' ''r''(''n'')을 갖는다. 마찬가지로, ''r''(''n'')-근사 알고리즘이 있는 문제는 ''r''(''n'')''-''근사 가능''하거나 근사 비율이 ''r''(''n'')''이라고 한다.^[12]^[13]

최소화 문제의 경우, 두 가지 다른 보장은 동일한 결과를 제공하며, 최대화 문제의 경우 ρ의 상대적 성능 보장은

r = \rho^{-1}

의 성능 보장과 같다.

성능 보장
	r-근사^[12]^[13]	ρ-근사	상대 오차^[13]	상대 오차^[12]	정규 상대 오차^[12]^[13]	절대 오차^[12]^[13]
최대: $f(x) \geq$	$r^{-1} \mathrm{OPT}$	$\rho \mathrm{OPT}$	$(1-c)\mathrm{OPT}$	$(1-c)\mathrm{OPT}$	$(1-c)\mathrm{OPT} + c\mathrm{WORST}$	$\mathrm{OPT} - c$
최소: $f(x) \leq$	$r \mathrm{OPT}$	$\rho \mathrm{OPT}$	$(1+c)\mathrm{OPT}$	$(1-c)^{-1}\mathrm{OPT}$	$(1-c)^{-1} \mathrm{OPT} + c\mathrm{WORST}$	$\mathrm{OPT} + c$

5. 2. 절대적 성능 보장

어떤 최적화 문제에 대해, 항상 ρ배를 벗어나지 않는 근사해를 구하는 알고리즘이 존재할 경우, 그 알고리즘을 '''ρ-근사 알고리즘'''이라고 부른다. 즉, 최적해가 OPT일 때, 근사 알고리즘 f(x)는 항상 다음을 만족해야 한다.^[5]

$\mathrm{OPT}(x) \leq f(x) \leq \rho \mathrm{OPT}(x)$ ( $\rho > 1$ 인 경우)
$\rho \mathrm{OPT}(x) \leq f(x) \leq \mathrm{OPT}(x)$ ( $\rho < 1$ 인 경우)

예를 들어, 최소 정점 덮개 문제에서 입력 그래프의 모든 간선이 적어도 하나의 선택된 정점을 포함하도록 가장 작은 정점 집합을 선택하는 알고리즘이 있다. 이 알고리즘은 덮이지 않은 간선을 찾고, 해당 간선의 양쪽 끝점을 덮개에 추가하고, 해당 정점에 인접한 모든 간선을 그래프에서 제거하는 과정을 반복한다. 입력 그래프의 모든 정점 덮개는 해당 과정에서 고려된 각 간선을 덮기 위해 서로 다른 정점을 사용해야 하므로(매칭), 생성된 정점 덮개는 최적의 덮개보다 최대 두 배 클 뿐이다. 즉, 이는 근사 계수가 2인 상수-인자 근사 알고리즘이다.

일부 근사 알고리즘의 경우 최적 결과에 대한 근사치에 대한 특정 속성을 증명하는 것이 가능하다. 예를 들어, '''ρ-근사 알고리즘''' ''A''는 인스턴스 ''x''에 대한 근사 솔루션 ''A''(''x'')의 값/비용, ''f''(''x'')가 최적 솔루션의 값 OPT의 인자 ''ρ''배보다 더 크지(또는 작지, 상황에 따라 다름) 않다고 증명된 알고리즘으로 정의된다.

:

\begin{cases}\mathrm{OPT} \leq f(x) \leq \rho \mathrm{OPT},\qquad\mbox{if } \rho > 1; \\ \rho \mathrm{OPT} \leq f(x) \leq \mathrm{OPT},\qquad\mbox{if } \rho < 1.\end{cases}

이 인자 ''ρ''는 ''상대적 성능 보장''이라고 한다. 근사 알고리즘은 모든 인스턴스 ''x''에 대해 다음이 증명된 경우 ''절대적 성능 보장'' 또는 ''유계 오차'' ''c''를 갖는다.

:

(\mathrm{OPT} - c) \leq f(x) \leq (\mathrm{OPT} + c).

마찬가지로, 인스턴스 ''x''에 대한 솔루션 ''y''의 ''성능 보장'' ''R''(''x,y'')는 다음과 같이 정의된다.

:

R(x,y) =  \max \left ( \frac{OPT}{f(y)}, \frac{f(y)}{OPT} \right ),

여기서 ''f''(''y'')는 인스턴스 ''x''에 대한 솔루션 ''y''의 값/비용이다. 분명히, 성능 보장은 1보다 크거나 같으며, ''y''가 최적의 솔루션인 경우에만 1과 같다. 알고리즘 ''A''가 최대 ''r''(''n'')의 성능 보장을 가진 솔루션을 반환하도록 보장하는 경우, ''A''는 ''r''(''n'')-근사 알고리즘이라고 하며 ''근사 비율'' ''r''(''n'')을 갖는다. 마찬가지로, ''r''(''n'')-근사 알고리즘이 있는 문제는 ''r''(''n'')''-''근사 가능''하거나 근사 비율이 ''r''(''n'')''이라고 한다.^[12]^[13]

최소화 문제의 경우, 두 가지 다른 보장은 동일한 결과를 제공하며, 최대화 문제의 경우 ρ의 상대적 성능 보장은

r = \rho^{-1}

의 성능 보장과 같다.

''절대적 성능 보장''

\Rho_A

는 문제의 가능한 모든 인스턴스에 대해 관찰되는 근사 비율 ''r''에 대한 가장 큰 경계이다. ''점근적 성능 비율''

R_A^\infty

는 문제 인스턴스 크기에 대한 하한 ''n''이 있는 ''절대적 성능 비율''과 같다. 이 두 가지 유형의 비율은 이 둘 사이의 차이가 중요한 알고리즘이 존재하기 때문에 사용된다.

성능 보장
	r-근사^[12]^[13]	ρ-근사	상대 오차^[13]	상대 오차^[12]	정규 상대 오차^[12]^[13]	절대 오차^[12]^[13]
최대: $f(x) \geq$	$r^{-1} \mathrm{OPT}$	$\rho \mathrm{OPT}$	$(1-c)\mathrm{OPT}$	$(1-c)\mathrm{OPT}$	$(1-c)\mathrm{OPT} + c\mathrm{WORST}$	$\mathrm{OPT} - c$
최소: $f(x) \leq$	$r \mathrm{OPT}$	$\rho \mathrm{OPT}$	$(1+c)\mathrm{OPT}$	$(1-c)^{-1}\mathrm{OPT}$	$(1-c)^{-1} \mathrm{OPT} + c\mathrm{WORST}$	$\mathrm{OPT} + c$

5. 3. 점근적 성능 비율

어떤 최적화 문제에 대해, 항상 ρ배를 벗어나지 않는 근사해를 구하는 알고리즘이 존재할 경우, 그 알고리즘을 '''ρ-근사 알고리즘'''이라고 부른다. 최적해가 OPT일 때, 근사 알고리즘 f(x)는 항상 다음을 만족해야 한다.^[5]

$\mathrm{OPT}(x) \leq f(x) \leq \rho \mathrm{OPT}(x)$ ( $\rho > 1$ 인 경우)
$\rho \mathrm{OPT}(x) \leq f(x) \leq \mathrm{OPT}(x)$ ( $\rho < 1$ 인 경우)

최소화 문제에서 ρ-근사 알고리즘과 r-근사 알고리즘(r ≥ 1)은 동일하며, 최대화 문제에서는 ρ-근사 알고리즘(ρ ≤ 1)의 ρ는 r-근사 알고리즘(r ≥ 1)의

r = \rho^{-1}

과 같다.

'''점근적 성능 비율'''

R_A^\infty

은 문제 인스턴스 크기에 대한 하한 ''n''이 있는 ''절대적 성능 비율''과 동일하며 다음과 같이 정의된다.

:

R_A^\infty = \inf \{ r \geq 1 \mid \exists n \in \mathbb{Z}^+, R_A(x) \leq r, \forall x, |x| \geq n\}.

성능 보장
	r-근사^[12]^[13]	ρ-근사	상대 오차^[13]	상대 오차^[12]	정규 상대 오차^[12]^[13]	절대 오차^[12]^[13]
최대: $f(x) \geq$	$r^{-1} \mathrm{OPT}$	$\rho \mathrm{OPT}$	$(1-c)\mathrm{OPT}$	$(1-c)\mathrm{OPT}$	$(1-c)\mathrm{OPT} + c\mathrm{WORST}$	$\mathrm{OPT} - c$
최소: $f(x) \leq$	$r \mathrm{OPT}$	$\rho \mathrm{OPT}$	$(1+c)\mathrm{OPT}$	$(1-c)^{-1}\mathrm{OPT}$	$(1-c)^{-1} \mathrm{OPT} + c\mathrm{WORST}$	$\mathrm{OPT} + c$

6. 근사 불가능성

근사 난해성 이론에 따르면, 특정 근사 비율을 갖는 효율적인 알고리즘의 부존재가 환원을 통해 증명될 수 있으며, 이는 P ≠ NP 추측과 같이 널리 받아들여지는 가설에 따라 조건부로 성립한다. 예를 들어, 거리 외판원 문제의 경우 P = NP가 아닌 이상 123/122 (약 1.008196) 미만의 근사 비율을 갖는 알고리즘은 존재할 수 없다.^[6] 이는 크리스토피데스의 1.5 근사 알고리즘과 함께 거리 외판원 문제의 근사 가능성 임계값(존재한다면)이 123/122와 1.5 사이에 있음을 시사한다.

1970년대부터 근사 난해성 결과가 증명되었으나, 당시에는 체계적인 이해가 부족했다. 1990년 독립 집합에 대한 페이게, 골드와서, 로바스, 사프라, 세게디의 결과^[7]와 PCP 정리^[8] 이후에야 비로소 근사 난해성 결과를 증명하는 현대적인 도구가 발견되었다. PCP 정리는 존슨이 1974년에 제시한 최대 SAT, 집합 커버, 독립 집합, 채색 문제에 대한 근사 알고리즘들이 P ≠ NP라고 가정할 때 모두 최적의 근사 비율을 달성한다는 것을 보여준다.^[9]

목적 함수 값과 최적해의 목적 함수 값의 비(근사도)가 특정 범위 내에 있음을 보장하는 알고리즘을 정밀도 보장 근사 알고리즘이라 부르며, 그렇지 않은 알고리즘은 발견적 기법(휴리스틱스)이라고 한다.

근사 알고리즘은 주로 NP-난해 문제에 대해 고안되지만, 다항 시간 내에 풀 수 있는 문제에 대해서도 더 빠른 계산을 위해 사용될 수 있다. 알고리즘 이론 분야에서는 다양한 문제에 대한 근사 알고리즘과 근사 불가능성에 관한 연구가 활발히 진행되고 있으며, PCP 정리가 대표적인 예이다.

최소 정점 피복 문제의 경우 근사도 2의 단순한 알고리즘이 존재하지만, 어떤 문제들은 상수 근사도를 갖는 다항 시간 알고리즘이 존재하지 않는다고 추측되기도 한다.

6. 1. 비 거리 공간 외판원 문제의 근사 불가능성

어떤 변에서는 삼각 부등식이 성립하지 않는 비 거리 공간 외판원 문제는, 어떤 최적화 문제에 대해 항상 p배를 벗어나지 않는 근사해를 구하는 알고리즘이 모든 p에 대해 존재하지 않는다.

비 거리 공간 외판원 문제 G를 정의한다. 마찬가지로 해밀턴 회로 판단 문제 G를 정의하고 G로부터 완전 그래프 G'을 V(G') = V(G)를 만족하도록 골라 가중치 w를 G에 포함된 변일 경우 1, 아닐 경우 kn을 부여한다.

이 때 "G에서 k 다항 시간 근사 해법을 찾을 수 있다"는 명제와 "G'에서 가중치가 kn보다 작은 해밀턴 경로를 찾을 수 있다"는 명제가 동치임을 증명한다.

G가 해밀턴 경로를 가지지 않는다면 모든 G'의 해밀턴 경로는 적어도 하나 이상의 G에 포함되지 않은 변을 사용해야 하므로 가중치가 kn보다 크다.

G가 해밀턴 경로를 가진다면 G'에서도 가중치가 n인 같은 해밀턴 경로 T*를 찾을 수 있다. 그렇다면 다항 시간 근사 해법에 의하면 해밀턴 경로는 최대 k · w(T*) = kn의 가중치를 가지게 된다.

따라서 비 거리 공간 외판원 문제 G의 근사 알고리즘이 존재한다면, 해밀턴 회로인지 판단하는 문제의 다항 시간 근사 해법이 존재하게 되어 NP-complete인 해밀턴 회로 판단 문제가 P임이 증명되었으므로 P=NP임이 증명되어 모순이다.^[6]

7. 응용 사례

크리스토피데스 알고리즘은 거리 공간 외판원 문제에서 근사해를 구하는 근사 알고리즘이다. 이 알고리즘은 최대 최적해의 3/2배 길이 안에 근사해를 구할 것을 보장하며, 1976년 니코스 크리스토피데스(Nicos Christofides)에 의해 개발되었다.^[10] 2017년까지도 특정 조건에서의 거리 공간 외판원 문제를 제외한 일반 거리 공간 외판원 문제를 해결하는 가장 좋은 근사해라고 알려져 있다.

모든 근사 알고리즘이 직접적인 실용적 응용에 적합한 것은 아니다. 일부 알고리즘은 까다로운 선형 계획법/반정부호 완화 (이는 자체적으로 타원체 알고리즘을 호출할 수 있음)를 해결하거나, 복잡한 자료 구조 또는 정교한 알고리즘 기술을 포함하여 구현 문제를 야기하거나, 실용적으로 큰 입력에서만 (정확한 알고리즘에 비해) 실행 시간 성능을 향상시킨다. 구현 및 실행 시간 문제 외에도, 근사 알고리즘이 제공하는 보증 자체가 실제로 고려할 만큼 충분히 강력하지 않을 수 있다. 실용적인 응용 분야에서 "즉시 사용"할 수 없다는 점에도 불구하고, 이러한 알고리즘 설계의 아이디어와 통찰력은 종종 실용적인 알고리즘에 다른 방식으로 통합될 수 있다. 이러한 방식으로, 매우 비용이 많이 드는 알고리즘 연구조차도 귀중한 통찰력을 얻을 수 있으므로 완전히 이론적인 추구는 아니다.

다른 경우, 초기 결과가 순전히 이론적인 관심사일지라도, 시간이 지남에 따라 이해도가 향상되면서 알고리즘이 더 실용적으로 개선될 수 있다. 이러한 예로는 유클리드 TSP에 대한 산지브 아로라(및 조셉 S. B. 미첼과 독립적으로)의 초기 PTAS가 있는데, 이는 $1+\epsilon$ 근사에 대해 $n^{O(1/\epsilon)}$ 의 실행 시간을 가졌다.^[10] 그러나 1년 이내에 이러한 아이디어가 임의의 상수 $\epsilon > 0$ 에 대해 거의 선형 시간인 $O(n\log n)$ 알고리즘에 통합되었다.^[11]

근사 알고리즘 중, 알고리즘이 출력하는 해의 목적 함수 값과 최적해의 목적 함수 값의 비(근사도)가 특정 범위 내에 들어가는 것이 보장되는 것을 특히 정밀도 보장 근사 알고리즘이라고 부른다. 그러한 보장이 없는 알고리즘은 발견적 기법(휴리스틱스)이라고 불린다. 전자와 후자를 구분하여, 전자만을 근사 알고리즘이라고 부르는 경우도 있다.

근사 알고리즘은 주로 NP-난해 문제에 대해 고안되지만, 다항 시간 내에 계산 가능한 문제에 대해서도, 더 빠른 계산 시간으로 해를 구하려는 목적으로 사용되기도 한다. 알고리즘 이론 분야에서 최근 중심적인 화제 중 하나이며, 다양한 문제에 대한 근사 알고리즘이 고안되고 있다. 또한, 가능한 근사도의 하한값을 나타내는 근사 불가능성에 관한 결과도 많이 얻어지고 있으며, PCP 정리 등이 유명하다.

예를 들어, 최소 정점 피복 문제에는 근사도 2의 단순한 알고리즘이 존재하지만, 근사도가 상수인 다항 시간 알고리즘이 존재하지 않는다고 여겨지는 문제도 있다.

8. 한계 및 현실성

모든 근사 알고리즘이 직접적인 실용적 응용에 적합한 것은 아니다. 일부 알고리즘은 까다로운 선형 계획법/반정부호 완화 (이는 자체적으로 타원체 알고리즘을 호출할 수 있음)를 해결하거나, 복잡한 자료 구조 또는 정교한 알고리즘 기술을 포함하여 구현 문제를 야기하거나, 실용적으로 큰 입력에서만 (정확한 알고리즘에 비해) 실행 시간 성능을 향상시킨다.^[10] 구현 및 실행 시간 문제 외에도, 근사 알고리즘이 제공하는 보증 자체가 실제로 고려할 만큼 충분히 강력하지 않을 수 있다. 실용적인 응용 분야에서 "즉시 사용"할 수 없다는 점에도 불구하고, 이러한 알고리즘 설계의 아이디어와 통찰력은 종종 실용적인 알고리즘에 다른 방식으로 통합될 수 있다. 이러한 방식으로, 매우 비용이 많이 드는 알고리즘 연구조차도 귀중한 통찰력을 얻을 수 있으므로 완전히 이론적인 추구는 아니다.

다른 경우, 초기 결과가 순전히 이론적인 관심사일지라도, 시간이 지남에 따라 이해도가 향상되면서 알고리즘이 더 실용적으로 개선될 수 있다. 이러한 예로는 유클리드 TSP에 대한 산지브 아로라 (및 조셉 S. B. 미첼과 독립적으로)의 초기 PTAS가 있는데, 이는 $1+\epsilon$ 근사에 대해 $n^{O(1/\epsilon)}$ 의 실행 시간을 가졌다.^[10] 그러나 1년 이내에 이러한 아이디어가 임의의 상수 $\epsilon > 0$ 에 대해 거의 선형 시간인 $O(n\log n)$ 알고리즘에 통합되었다.^[11]

참조

_[1] 서적 The design of approximation algorithms http://www.designofa[...] Cambridge University Press 2011
_[2] 간행물 Approximation algorithms for scheduling unrelated parallel machines 1990-01-01
_[3] 서적 Proceedings of the twenty-third annual ACM symposium on Theory of computing - STOC '91 ACM Press 1991
_[4] 간행물 Improved Approximation Algorithms for Maximum Cut and Satisfiability Problems Using Semidefinite Programming 1995-11
_[5] 간행물 Vertex cover might be hard to approximate to within 2−ε 2008-05-01
_[6] 간행물 New inapproximability bounds for TSP 2015-12-01
_[7] 간행물 Interactive Proofs and the Hardness of Approximating Cliques 1996-03
_[8] 간행물 Probabilistic Checking of Proofs: A New Characterization of NP 1998-01
_[9] 간행물 Approximation algorithms for combinatorial problems 1974-12-01
_[10] 서적 Proceedings of 37th Conference on Foundations of Computer Science 1996-10
_[11] 서적 Proceedings 38th Annual Symposium on Foundations of Computer Science 1997-10
_[12] 서적 Complexity and Approximation: Combinatorial Optimization Problems and their Approximability Properties
_[13] 서적 On the Approximability of NP-complete Optimization Problems https://www.csc.kth.[...]
_[14] 간행물 Some Optimal Inapproximability Results http://www.nada.kth.[...]
_[15] 서적 The Design of Approximation Algorithms
_[16] 서적 近似アルゴリズム丸善出版 2012-07-17
_[17] 서적 計算困難問題に対するアルゴリズム理論: 組合せ最適化・ランダマイゼ-ション・近似・ヒュ-リスティクス丸善出版 2016-01-10
_[18] 서적 近似アルゴリズム: 離散最適化問題への効果的アプローチ共立出版 2019-06-27

본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com